package exercise49;

/**
 * @Author Fizz Pu
 * @Date 2021/8/11 下午2:26
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

// 1. 求和
// 2. 中序遍历 相减pre去即可
// 前缀和
public class Lee538 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(8);
        TreeNode node3 = new TreeNode(1);
        TreeNode node4 = new TreeNode(3);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;

        new Lee538().convertBST(root);
    }
    public TreeNode convertBST(TreeNode root) {
        update(root, getSum(root));
        return root;
    }

    // 前序列
    private int getSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return root.val + getSum(root.left) + getSum(root.right);
    }

    // 中序列
    int preSum = 0;
    private void update(TreeNode root, int sums) {
        if (root == null) {
            return;
        }

        update(root.left, sums);
        // 开始更新
        int tmp = root.val;
        root.val = sums - preSum;
        // 更新遍历过的和
        this.preSum += tmp; // this.preSum = root.val;
        update(root.right, sums);
    }
}
